|
In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it is an assignment of colors to vertices of an oriented graph that * is proper: no two adjacent vertices get the same color, and * respects the orientation: if (''x'', ''y'') and (''u'', ''v'') are arcs of the graph then it is not possible that colors of ''x'' and ''v'' and of ''y'' and ''u'' are the same. An ''oriented chromatic number'' of a graph ''G'' is the least number of colors needed in an oriented coloring; it is usually denoted by . The same definition can be extended to undirected graphs, as well, by defining the oriented chromatic number of an undirected graph to be the largest oriented chromatic number of any of its orientations.〔.〕 == Examples == The oriented chromatic number of a directed 5-cycle is five. If the cycle is colored by four or fewer colors, then either two adjacent vertices have the same color, or two vertices two steps apart have the same color. In the latter case, the edges connecting these two vertices to the vertex between them are inconsistently oriented: both have the same pair of colors but with opposite orientations. Thus, no coloring with four or fewer colors is possible. However, giving each vertex its own unique color leads to a valid oriented coloring. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Oriented coloring」の詳細全文を読む スポンサード リンク
|